Previous | Index | Next |

Iterators

Iterators are a generalization of a position (pointer) in a data structure that allow a programmer to work with different data structures (containers) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, we need to formalize not just the interfaces but also the semantics and complexity assumptions of iterators.

Since iterators are a generalization of pointers, their semantics is a generalization of the semantics of pointers. Depending on the operations defined on them, there are five categories of iterators: input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators. Forward iterators satisfy all the requirements of the input and output iterators and can be used whenever either kind is specified. Bidirectional iterators satisfy all the requirements of the forward iterators and can be used whenever a forward iterator is specified. Random access iterators satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified.

Both InputIterator and OutputIterator extends the Iterator api interface.

For any iterator type there is an iterator value that points past the last element of a corresponding container. These values are called past-the-end values. Values of the iterator for which the get() and put(Object) is defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable. Iterators might also have singular values that are not associated with any container. For example, after the declaration of an uninitialized iterator x (as with Iterator x;), x should always be assumed to have a singular value. Results of most expressions are undefined for singular values. The only exception is an assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable and past-the-end values are always non-singular.

An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of next() to i that makes i.cmp(j) return true. If i and j refer to the same container, then either j is reachable from i, or i is reachable from j, or both (i == j).

Most of the library's algorithmic method that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i,i) is an empty range; in general, a range [i,j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i,j) is valid if and only if j is reachable from i. The result of the application of the algorithms in the library to invalid ranges is undefined.

All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.


Previous | Index | Next |